package cn.lbd.arithmetic.leetcode.editor.cn.test;

import java.util.Arrays;

public class MergeSort {
    public static void merge(int[] arr, int[] tmp, int lStart, int rStart, int rEnd) {
        int lEnd = (lStart + rEnd) / 2;
        int tmpIndex = lStart;
        int arrLength = rEnd - lStart + 1;
        while (lStart <= lEnd && rStart <= rEnd) {
            if (arr[lStart] <= arr[rStart]){
                tmp[tmpIndex++] = arr[lStart++];
            }else {
                tmp[tmpIndex++] = arr[rStart++];
            }
        }
        while(lStart <= lEnd) {
            tmp[tmpIndex++] = arr[lStart++];
        }
        while(rStart <= rEnd) {
            tmp[tmpIndex++] = arr[rStart++];
        }
        for (int i = 0; i < arrLength; i++,rEnd--) {
            arr[rEnd] = tmp[rEnd];
        }
    }

    public static void sort(int[] arr, int[] tmp, int lStart, int rEnd) {
        int center = (lStart + rEnd) / 2;
        if (lStart < rEnd) {
            sort(arr, tmp, lStart, center);
            sort(arr, tmp, center + 1, rEnd);
            merge(arr, tmp, lStart, center + 1, rEnd);
        }
    }

    public static void main(String[] args) {
        int arr[] = {5, 3, 4, 2, 1, 6};
        int tmp[] = new int[arr.length];
        sort(arr, tmp, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
